package LC;

/**
 * https://leetcode.com/problems/validate-binary-search-tree/description/
 * Given a binary tree, determine if it is a valid binary search tree (BST).
 * Assume a BST is defined as follows:
 * The left subtree of a node contains only nodes with keys less than the node's key.
 * The right subtree of a node contains only nodes with keys greater than the node's key.
 * Both the left and right subtrees must also be binary search trees.
 * Binary tree [2,1,3], return true.
 * Binary tree [1,2,3], return false.
 */
public class LC_098_ValidateBinarySearchTree_BST_BinaryTree {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(-1);
        head.right = new TreeNode(2);
        System.out.println(Solution.isValidBST(head));
        System.out.println(Solution_2.isValidBST(head));
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static boolean isValidBST(TreeNode root) {
            return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
        }

        static boolean isValidBST(TreeNode p, double min, double max) {
            if (p == null)
                return true;

            if (p.val <= min || p.val >= max)
                return false;

            return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max);
        }
    }

    static class Solution_2 {
        static boolean isValidBST(TreeNode root) {
            return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
        }

        static boolean isValidBST(TreeNode p, double min, double max) {
            return p == null || !(p.val <= min) && !(p.val >= max) && isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max);
        }
    }
}
